package leetcode_动态规划._07背包问题._01背包;

/**
 * @author yzh
 * @data 2021/3/18 14:58
 * 目标和
 * 思路：
 *   看了解题方法才想到原来是怎么做的
 *   把整数集合看作 p，负数集合看作 q
 *   那么根据题目要求，p - q = target
 *   而 p + q = sum
 *   所以得出 p = (target + sum) / 2
 *   题目就变成了从数组中找出一个集合，是的这个集合相加为 (target + sum) / 2
 *
 */
public class _494 {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 1, 1, 1};
        int S = 3;
        System.out.println(new _494().findTargetSumWays(nums, S));
    }

    public int findTargetSumWays(int[] nums, int S) {
        int target = 0;
        for (int num : nums) {
            target += num;
        }
        if ((S + target) % 2 == 1) {
            return 0;
        }
        return dfs(nums, 0, target);
    }
    public int dfs(int[] nums, int begin, int target) {
        if (target == 0) {
            return 1;
        }
        int res = 0;
        for (int i = begin; i < nums.length; i++) {
            if (target < nums[i]) {
                continue;
            }
            res += dfs(nums, i + 1, target - nums[i]);
        }
        return res;
    }

    public int findTargetSumWays_perfect(int[] nums, int S) {
        int target = 0;
        for (int num : nums) {
            target += num;
        }
        if (S > target ||  (target + S) % 2 == 1) {
            return 0;
        }
        target = (S + target) >>> 1;
        int[] dp = new int[target + 1];
        dp[0] = 1; // 没有也是一种方法
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; --j) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}
